Nim game

Time: O(1); Space: O(1); easy

You are playing the following Nim Game with your friend:

  • There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones.

  • The one who removes the last stone will be the winner.

  • You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game.

Write a function to determine whether you can win the game given the number of stones in the heap.

Example 1:

Input: n = 4

Output: False

Explanation:

  • If there are 4 stones in the heap, then you will never win the game;

  • No matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

[1]:

class Solution1(object):
    def canWinNim(self, n) -> bool:
        """
        :type n: int
        :rtype: bool
        """
        return n % 4 != 0

[2]:

s = Solution1()
n = 4
assert s.canWinNim(n) == False
n = 3
assert s.canWinNim(n) == True